package com.lw.leetcode.str.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1202. 交换字符串中的元素
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/30 11:26
 */
public class SmallestStringWithSwaps {


    public static void main(String[] args) {
        SmallestStringWithSwaps test = new SmallestStringWithSwaps();

        // "abcd"
        String str = "dcab";
        List<List<Integer>> pairs = new ArrayList<List<Integer>>() {{
            add(Arrays.asList(0,3));
            add(Arrays.asList(1,2));
            add(Arrays.asList(0,2));
        }};

        String string = test.smallestStringWithSwaps(str, pairs);
        System.out.println(string);
    }

    private Map<Integer, List<Integer>> map = new HashMap<>();
    private Set<Integer> all = new HashSet<>();
    private char[] chars;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        chars = s.toCharArray();
        int size = pairs.size();
        for (int i = 0; i < size; i++) {
            List<Integer> list = pairs.get(i);
            int a = list.get(0);
            int b = list.get(1);
            map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
            map.computeIfAbsent(b, v -> new ArrayList<>()).add(a);
        }
        for (int key : map.keySet()) {
            if (all.contains(key)) {
                continue;
            }
            List<Integer> indexList  = new ArrayList<>();
            int[] arr = new int[26];
            find(indexList, arr, key);
            Collections.sort(indexList);
            int index = 0;
            for (int i = 0; i < 26; i++) {
                int value = arr[i];
                for (int j = 0; j < value; j++) {
                    chars[indexList.get(index++)] = (char) (i + 'a');
                }
            }
        }
        return String.valueOf(chars);
    }

    private void find(List<Integer> indexList, int[] arr, int key) {
        List<Integer> list = map.get(key);
        if (list == null) {
            return;
        }
        for (int value : list) {
            if (all.contains(value)) {
                continue;
            }
            all.add(value);
            arr[chars[value] - 'a']++;
            indexList.add(value);
            find(indexList, arr, value);
        }
    }

}
